package cn.edu.xjtu.competiton.力扣.双周赛.biweekly87;

import java.util.Arrays;

/**
 * @author Hydrion-QLz
 * @date 2022-09-17 22:59
 * @description
 */
public class third {
    public static void main(String[] args) {
        int[] arr = {1, 0, 2, 1, 3};
        int[] arr1 = {1, 2};
        System.out.println(Arrays.toString(smallestSubarrays3(arr)));
    }

    /**
     * 空间爆了（但是好像还是暴力，不过少计算了）
     *
     * @param nums
     * @return
     */
    public static int[] smallestSubarrays(int[] nums) {
        if (nums.length == 0) {
            return new int[0];
        }
        int[][] prefix = new int[nums.length][nums.length];
        for (int i = 0; i < nums.length; i++) {
            prefix[0][i] = nums[i];
            prefix[i][i] = nums[i];
        }
        for (int i = 1; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                prefix[i][j] = prefix[i - 1][j - 1] | nums[j];
            }
        }

        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            int max = nums[i];
            int maxLength = 1;
            for (int j = i + 1; j < nums.length; j++) {
                int val = prefix[i][j];
                if (val > max) {
                    maxLength = j - i + 1;
                    max = val;
                }
            }
            result[i] = maxLength;
        }
        return result;
    }


    /**
     * 类似暴力，还是会超时
     *
     * @param nums
     * @return
     */
    public static int[] smallestSubarrays3(int[] nums) {
        if (nums.length == 0) {
            return new int[0];
        }
        int[] prefix = new int[nums.length];

        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            prefix[i] = nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                prefix[j] = prefix[j - 1] | nums[j];
            }
            int max = nums[i];
            int maxLength = 1;
            for (int j = i + 1; j < nums.length; j++) {
                int val = prefix[j];
                if (val > max) {
                    maxLength = j - i + 1;
                    max = val;
                }
            }
            result[i] = maxLength;
        }
        return result;
    }

    public static int[] smallestSubarrays2(int[] nums) {
        if (nums.length == 0) {
            return new int[0];
        }
        int[] prefix = new int[nums.length + 1];
        prefix[0] = 0;
        for (int i = 0; i < nums.length; i++) {
            prefix[i + 1] = prefix[i] | nums[i];
        }

        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            int max = nums[i];
            int maxLength = 1;
            for (int j = i + 1; j < nums.length; j++) {
                int val = prefix[j + 1] | prefix[i];
                if (val > max) {
                    maxLength = j - i + 1;
                    max = val;
                }
            }
            result[i] = maxLength;
        }
        return result;
    }

    /**
     * 暴力解法，超时
     *
     * @param nums
     * @return
     */
    public static int[] smallestSubarrays1(int[] nums) {
        if (nums.length == 0) {
            return new int[0];
        }
//        int[] prefix = new int[nums.length];
//        prefix[0] = nums[0];
//        for (int i = 1; i < nums.length; i++) {
//            prefix[i] = prefix[i - 1] | nums[i];
//        }

        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            int max = nums[i];
            int maxLength = 1;
            int curr = nums[i];
            int length = 1;
            for (int j = i + 1; j < nums.length; j++) {
                length++;
                curr = curr | nums[j];
                if (curr > max) {
                    maxLength = length;
                    max = curr | nums[j];
                }
            }
            result[i] = maxLength;
        }
        return result;
    }
}
